home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / c_news / 10 / database / bplus.doc < prev    next >
Text File  |  1987-10-13  |  23KB  |  583 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.                                THE B-PLUS PROGRAM
  8.                          A B-TREE INDEXING FILE MODULE
  9.                                FOR C PROGRAMMERS
  10.                                        by
  11.                              Hunter and Associates
  12.  
  13.  
  14.  
  15.               B-PLUS is a versatile, carefully designed module for C
  16.          programmers who need a fast, efficient program for indexing
  17.          data files.  B-PLUS allows data records to be retrieved based
  18.          on a key value without regard to their position in the data
  19.          file.  The data records can also be accessed in sequential
  20.          order in either a forward and reverse direction.
  21.  
  22.               The B-PLUS Program Module is based on the famous and
  23.          widely used b-tree algorithm and has a number of useful
  24.          extensions which are not found in many programs of this type.
  25.          Some of its features are the following:
  26.  
  27.               - Variable length keys are allowed
  28.  
  29.               - File size limited only by DOS or by disk space
  30.  
  31.               - All functions are non-recursive so very little stack
  32.                 space is required
  33.  
  34.               - The most recently used key values are stored in a
  35.                 cache buffer in main memory for fast access
  36.  
  37.               - Duplicate keys are allowed
  38.  
  39.               The B-PLUS program has been tested using the Microsoft C
  40.          Compiler, Versions 4.0 and 5.0 (Beta), and the Borland Turbo
  41.          C Compiler Version 1.0.  The compiled object file is less
  42.          than 9.4K bytes in length for these compilers.
  43.  
  44.  
  45.  
  46.          LICENSE AND REGISTRATION
  47.  
  48.               B-PLUS is distributed as a "shareware" program.  Please
  49.          help us get it known by giving unmodified copies of the
  50.          program and documentation to other programmers who may find
  51.          B-PLUS useful.
  52.  
  53.               B-PLUS is copyright (C) 1987 by Hunter and Associates.
  54.          It is not public domain or free software.  Non-registered
  55.          users are granted a limited license to use B-PLUS on a trial
  56.  
  57.  
  58.                                      Page 1
  59.  
  60.  
  61.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  62.          -------------------------------------------------------------
  63.  
  64.  
  65.          basis for determining whether or not it is suitable for their
  66.          needs.  Registration permits the use of B-PLUS on one CPU and
  67.          allows the use of the compiled B-PLUS modules in programs for
  68.          general sale and/or distribution.
  69.  
  70.               The registration fee is $25 or $35.  Users who pay the
  71.          $35 fee will be sent a disk containing a fully commented
  72.          listing of the latest source code, the user documentation,
  73.          and a number of useful sample programs.  Users who pay the
  74.          $25 fee are not sent a new disk but are included in the
  75.          mailing list for announcements about both current and future
  76.          products.  Your prompt registration of your copy of the B-
  77.          PLUS program is appreciated.
  78.  
  79.               A trial disk with supporting documentation is available
  80.          directly from Hunter and Associates for $10.
  81.  
  82.               Register your usage of B-PLUS by sending the registra-
  83.          tion fee to:
  84.  
  85.                         Hunter and Associates
  86.                         7050 NW Zinfandel Lane
  87.                         Corvallis, OR  97330
  88.                         Telephone: (503) 745-7186
  89.  
  90.          Your comments regarding the B-PLUS program or any suggestions
  91.          you have for extensions or for other programs that would be
  92.          useful to you are welcomed.
  93.  
  94.               Hunter and Associates makes no warranties whatsoever
  95.          regarding the B-PLUS computer programs or the supporting
  96.          documentation.
  97.  
  98.  
  99.  
  100.          USING B-PLUS IN YOUR PROGRAMS
  101.  
  102.               The B-PLUS File Indexing Module contains twelve
  103.          functions that handle the retrieval of data records by key
  104.          value.  The keys that are used to locate records are null
  105.          terminated strings.  The data structures and constants that
  106.          are used are defined in the header file bplus.h.
  107.  
  108.               If the data record field that you want to use as a key
  109.          contains numeric data, you can use one of the library
  110.          conversion routines (fcvt, evct, sprintf) to convert the data
  111.          to string format.
  112.  
  113.               The connection between a key and its reference is
  114.  
  115.  
  116.                                      Page 2
  117.  
  118.  
  119.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  120.          -------------------------------------------------------------
  121.  
  122.  
  123.          formalized as a structure of type ENTRY.  This structure
  124.          contains three elements:
  125.  
  126.          typedef struct
  127.            {
  128.              RECPOS   idxptr;         /* long pointer to next index
  129.                                          level                      */
  130.              RECPOS   recptr;         /* long pointer to the file
  131.                                          position of data record    */
  132.              char     key[MAXKEY];    /* with this key value        */
  133.            } ENTRY;
  134.  
  135.               The application program uses only the recptr and key[]
  136.          fields.  The idxptr is used and maintained by the B-PLUS
  137.          modules.
  138.  
  139.               A variable of type IX_DESC is declared for each open
  140.          index file.  See the header file bplus.h if you are
  141.          interested in the elements of this structure.  ENTRY and
  142.          IX_DESC are the only two data types that are normally used by
  143.          application programs.
  144.  
  145.               Here is a sample program stub which calls the open_index
  146.          and find_index subroutines.
  147.  
  148.          Example:
  149.  
  150.            #include "bplus.h"
  151.            main()
  152.              {
  153.                 ENTRY    e;
  154.                 IX_DESC  names;
  155.  
  156.                 /* open index file called NAMES.IDX */
  157.  
  158.                 open_index("NAMES.IDX", &names, 0);
  159.  
  160.                 /* find an index record for John Smith */
  161.  
  162.                 strcpy(e.key, "SMITH JOHN");
  163.                 if(find_key(&e, &names))
  164.                   printf("Data record address is %ld", e.recptr);
  165.                 else
  166.                   printf("Cannot find record for that key");
  167.               }
  168.  
  169.  
  170.          Each of the twelve subroutines is now described.
  171.  
  172.  
  173.  
  174.                                      Page 3
  175.  
  176.  
  177.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  178.          -------------------------------------------------------------
  179.  
  180.  
  181.  
  182.          int cdecl open_index(name, pix, dup);
  183.  
  184.               char *name;         File path name
  185.               IX_DESC *pix;       Pointer to index file variable
  186.               int dup;            0 - no duplicate keys allowed
  187.                                   1 - allow duplicate keys
  188.  
  189.               Description:  The open_index function is used to open
  190.               and initialize an existing index file specified by name
  191.               and prepares the file for subsequent reading or writing.
  192.               The file structure variable pix is defined in the
  193.               application program.  Duplicate keys are allowed or not
  194.               allowed depending on whether dup has the value of 0 or
  195.               1.  The open_index function returns the value IX_OK (1)
  196.               if the file is opened successfully.  If the file cannot
  197.               be opened, an error message is displayed and the program
  198.               is aborted.
  199.  
  200.  
  201.  
  202.          int cdecl make_index(name, pix, dup);
  203.  
  204.               char *name;         File path name
  205.               IX_DESC *pix;       Pointer to index file variable
  206.               int dup;            0 - no duplicate keys allowed
  207.                                   1 - allow duplicate keys
  208.  
  209.               Description:  The make_index function is used to create
  210.               and initialize a new index file specified by name and to
  211.               prepare the file for subsequent reading or writing.  If
  212.               a file of this name already exists, its contents are
  213.               destroyed when the new file is created.  The file
  214.               structure variable pix is defined in the application
  215.               program.  Duplicate keys are allowed or not allowed
  216.               depending on whether dup has the value of 0 or 1.  The
  217.               make_index function returns the value IX_OK (1) if the
  218.               file is created successfully.  If the file cannot be
  219.               created, an error message is displayed and the program
  220.               is aborted.
  221.  
  222.  
  223.  
  224.          int cdecl close_index(pix);
  225.  
  226.               IX_DESC *pix;       Pointer to index file variable
  227.  
  228.               Description:  The close_index file function clears the
  229.               internal cache buffer and closes the specified index
  230.  
  231.  
  232.                                      Page 4
  233.  
  234.  
  235.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  236.          -------------------------------------------------------------
  237.  
  238.  
  239.               file.  It is very important that each index file be
  240.               closed.  Otherwise data that is stored in the internal
  241.               cache buffer may be lost and the index file may not be
  242.               properly updated.  The close_index function returns the
  243.               value IX_OK (1) if the file is successfully closed.
  244.  
  245.  
  246.  
  247.          int cdecl find_key(pe, pix);
  248.  
  249.               ENTRY *pe;          Pointer to variable of type ENTRY
  250.               IX_DESC *pix;       Pointer to index file variable
  251.  
  252.               Description:  The find_key function searches the index
  253.               file for the key value contained in pe.key.  If an exact
  254.               match is found, the value IX_OK (1) is returned and the
  255.               location of the data record with this key value is
  256.               stored in pe.recptr.  If an exact match is not found,
  257.               the value IX_FAIL (0) is returned and pe.recptr is
  258.               undefined.  If the index file contains duplicate keys,
  259.               the first key is always found.
  260.  
  261.  
  262.  
  263.          int cdecl locate_key(pe, pix);
  264.  
  265.               ENTRY *pe;          Pointer to variable of type ENTRY
  266.               IX_DESC *pix;       Pointer to index file variable
  267.  
  268.               Description:  The locate key function searches the index
  269.               file for the first key value which is equal to or
  270.               greater than that stored in pe.key.  The location of the
  271.               data record which is equal to or greater than pe.key is
  272.               stored in pe.recptr.  This function can be used to
  273.               locate an entry in the index file when only part of the
  274.               key value is known.  If the index file contains
  275.               duplicate keys, locate_key will locate the first key.
  276.               The following values are returned by locate_key:
  277.  
  278.                    IX_OK  -  the value (1) is returned if an exact
  279.                              match is found
  280.  
  281.                    IX_FAIL - the value (0) is returned if an exact
  282.                              match is not found
  283.  
  284.                    EOIX  -   the value (-2) is returned for end of
  285.                              index if the search key is greater than
  286.                              all keys in the index file and pe.recptr
  287.                              is undefined.
  288.  
  289.  
  290.                                      Page 5
  291.  
  292.  
  293.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  294.          -------------------------------------------------------------
  295.  
  296.  
  297.  
  298.          int cdecl add_key(pe, pix);
  299.  
  300.               ENTRY *pe;          Pointer to variable of type ENTRY
  301.               IX_DESC *pix;       Pointer to index file variable
  302.  
  303.               Description:  The add_key function adds new entries to
  304.               the index file.  The calling program stores the key
  305.               value in pe.key and the data record address in
  306.               pe.recptr.  Add_key first looks to see if an entry with
  307.               this key already exists in the index file.  If no entry
  308.               with this key exists, the new entry is added.  If an
  309.               entry with this key already exists, the new entry is
  310.               added only if duplicate keys are allowed (as defined by
  311.               the open_index function).  If the entry is successfully
  312.               added, IX_OK (1) is returned; otherwise IX_FAIL (0) is
  313.               returned.
  314.  
  315.  
  316.  
  317.          int cdecl delete_key(pe, pix);
  318.  
  319.               ENTRY *pe;          Pointer to variable of type ENTRY
  320.               IX_DESC *pix;       Pointer to index file variable
  321.  
  322.               Description:  The delete_key function deletes entries
  323.               in the index file.  The key to be deleted is stored in
  324.               pe.key.  If duplicate records are allowed, the
  325.               corresponding data record address must also be stored in
  326.               pe.recptr.  In this case, delete key needs the record
  327.               number to distinguish entries.  If there are not
  328.               duplicate entries, this field is ignored.  If the entry
  329.               is successfully deleted, IX_OK (1) is returned;
  330.               otherwise IX_FAIL (0) is returned.  The space that was
  331.               occupied by the entry is marked as free for reused by
  332.               B_PLUS.
  333.  
  334.  
  335.  
  336.          int cdecl first_key(pix);
  337.  
  338.               IX_DESC *pix;       Pointer to index file variable
  339.  
  340.               Description:  The first_key function positions the index
  341.               file pointer to the beginning of the index file.  The
  342.               function next_key can then be used to list the file in
  343.               key order.  The first_key function returns the value
  344.               IX_OK (1).
  345.  
  346.  
  347.  
  348.                                      Page 6
  349.  
  350.  
  351.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  352.          -------------------------------------------------------------
  353.  
  354.  
  355.          int cdecl last_key(pix);
  356.  
  357.               IX_DESC *pix;       Pointer to index file variable
  358.  
  359.               Description:  The last_key function positions the index
  360.               file pointer at the end of the index file.  The function
  361.               previous_key can then be used to list the file in
  362.               reverse key order.  The last_key function returns the
  363.               value IX_OK (1).
  364.  
  365.  
  366.  
  367.          int cdecl next_key(pe, pix);
  368.  
  369.               ENTRY *pe;          Pointer to variable of type ENTRY
  370.               IX_DESC *pix;       Pointer to index file variable
  371.  
  372.               Description:  The next_key function returns the next
  373.               entry in the index file.  Before next_key is called, the
  374.               index file pointer should be positioned by the function
  375.               first_key, find_key, or locate_key.  Next_key can be
  376.               used to locate the desired data record when duplicate
  377.               keys are allowed.  Another use is to process files
  378.               sequential.  Next key returns the value IX_OK (1) if the
  379.               next key is present and the value EOIX (-2) when the
  380.               file pointer is at the end of the index file.  The
  381.               following program processes an indexed file
  382.               sequentially:
  383.  
  384.               #include "bplus.h"
  385.               main()
  386.                 {
  387.                   ENTRY e;
  388.                   IX_DESC names;
  389.  
  390.                   /* open the index file */
  391.                   open_index("names.idx", &names);
  392.  
  393.                   /* now process the file sequentially */
  394.                   first_key(&names);
  395.                   ret = next_key(&e, &names);
  396.                   while (ret == IX_OK)
  397.                     {
  398.                       /* the data record location is e.recptr */
  399.                       /* the program would retrieve and process */
  400.                       ret = next_key(&e, &names);
  401.                     }
  402.  
  403.                   /* remember to always close open files */
  404.  
  405.  
  406.                                      Page 7
  407.  
  408.  
  409.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  410.          -------------------------------------------------------------
  411.  
  412.  
  413.                   close_index(&names);
  414.                 }
  415.  
  416.  
  417.  
  418.          int cdecl prev_key(pe, pix);
  419.  
  420.               ENTRY *pe;          Pointer to variable of type ENTRY
  421.               IX_DESC *pix;       Pointer to index file variable
  422.  
  423.               Description:  The prev_key function returns the previous
  424.               entry in the index file.  Before prev_key is called, the
  425.               index file pointer should be positioned by the function
  426.               last_key, find_key, or locate_key.  Prev_key can be used
  427.               to process files sequentially is reverse order.
  428.               Prev_key returns the value IX_OK (1) if there is a
  429.               previous key and the value EOIX (-2) when the file
  430.               pointer is at the beginning of the index file.
  431.  
  432.  
  433.  
  434.          int cdecl find_exact(pe, pix);
  435.  
  436.               ENTRY *pe;          Pointer to variable of type ENTRY
  437.               IX_DESC *pix;       Pointer to index file variable
  438.  
  439.               Description:  The find_exact function searches the index
  440.               file for the key value contained in pe.key and the data
  441.               record position stored in pe.recptr.  If an exact match
  442.               is found for both of these values, the value IX_OK (1)
  443.               is returned, and the internal index file pointer is set
  444.               to that position in the index file.  If an exact match
  445.               is not found, the value IX_FAIL (0) is returned.
  446.  
  447.  
  448.  
  449.          TAILORING OR CHANGING B-PLUS
  450.  
  451.               Most applications can use the B-PLUS program as it is
  452.          distributed by Hunter and Associates without any changes.  It
  453.          allows multiple, large data files to be indexed in a fast,
  454.          efficient manner.  However, a description of the values that
  455.          can be changed to tailor B-PLUS are given in this section.
  456.  
  457.               An index tree becomes full when no more entries can be
  458.          added to the tree.  This is the case when adding another
  459.          entry to the tree would cause the tree to grow larger than
  460.          its maximum allowed height.  This height depends on the size
  461.          of the index blocks and the average size of the keys used by
  462.  
  463.  
  464.                                      Page 8
  465.  
  466.  
  467.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  468.          -------------------------------------------------------------
  469.  
  470.  
  471.          the data files.  The minimum capacity of a b-tree index is
  472.          given by the following formula:
  473.  
  474.               C = (B / E + 1) * (B / (2 * E)  + 1) ** (H - 1)
  475.  
  476.          where C is the number of entries in the index file, B is the
  477.          block size in bytes, E is the average size of an ENTRY in
  478.          bytes, and H is the maximum tree height.
  479.  
  480.               The maximum key size is defined by MAXKEY and is set at
  481.          100.  The block size is 1024 bytes as defined by IXB_SIZE.
  482.          Ten bytes are used by pointers so 1014 bytes are used by
  483.          entries.  The size of an ENTRY is 9 + the key length.
  484.  
  485.               Thus, if the average key length is 11, an average ENTRY
  486.          is 20 bytes long and the minimum number of entries that can
  487.          be contained in a tree of height 4 is:
  488.  
  489.               C = (1014 / 20 + 1) * (1014 / 40 + 1) ** 3
  490.                 = 945,072
  491.  
  492.          If the average ENTRY is 40 bytes long, the minimum number of
  493.          entries that can be contained in a tree of height 4 is
  494.          67,384.  The corresponding values for a tree of height 3 are
  495.          35,896 and 4927, respectively.
  496.  
  497.               The maximum tree height is determined by MAX_LEVELS and
  498.          is set to eight.  Very little memory space is used by
  499.          allowing the maximum tree height to be this large.  B-PLUS
  500.          increases the height of the tree dynamically as required by
  501.          number of records in the data file.
  502.  
  503.               If your application does not use long keys and your
  504.          files are not huge, IXB_SIZE can be changed to 512 bytes with
  505.          only a slight degradation in performance.
  506.  
  507.               The root of an open index file is always memory resident
  508.          as defined by the variable of type IX_DESC.  A dynamic pool
  509.          of cache buffers is used for other index blocks of the tree.
  510.          The number of blocks in the pool is defined by NUM_BUFS with
  511.          a default value of 8.  Each memory block is sizeof(IXB_SIZE)
  512.          + 8 bytes in length so approximately 8K of memory is used for
  513.          cache storage of index blocks.  If the number of index files
  514.          that are open simultaneously is larger than 4, you may want
  515.          to increase NUM_BUFS.  If the usage of memory is critical,
  516.          the number of buffers can be decreased.  However, NUM_BUFS
  517.          must be at least 2.  In general, the speed of file access can
  518.          be expected to improve if the number of buffers is increased
  519.          since more of the index file is memory resident.
  520.  
  521.  
  522.                                      Page 9
  523.  
  524.  
  525.          HUNTER AND ASSOCIATES            B-PLUS FILE INDEXING PROGRAM
  526.          -------------------------------------------------------------
  527.  
  528.  
  529.  
  530.               Because some indices are always memory resident, and
  531.          because the DOS Operating System requires it, it is very
  532.          important that all open index files be closed before an
  533.          application program terminates.
  534.  
  535.               As stated earlier, the B-PLUS program has been tested
  536.          using Microsoft's Optimizing C Compiler, Version 4 and 5, and
  537.          Borland's Turbo C, Version 1.0.  However, standard K & R
  538.          programming guidelines are followed so B-PLUS should be able
  539.          to be used with other C Compilers with little modification.
  540.          Since B-PLUS is non-recursive, the usage of stack space does
  541.          not change dynamically.  It is recommend that the B-PLUS
  542.          program be compiled without stack checking.  For Microsoft C,
  543.          the /Ox option can be used to maximize speed and minimize
  544.          code size.
  545.  
  546.  
  547.  
  548.          ACKNOWLEDGMENTS AND REFERENCES
  549.  
  550.               The following reference materials were used and helpful
  551.          in writing the B-PLUS program:
  552.  
  553.               Wirth, Niklaus:
  554.                      Algorithms + Data Structures = Programs
  555.                      Prentice Hall (1976)
  556.  
  557.               Hunt, William James:
  558.                      The C Toolbox
  559.                      (Serious C Programming for the IBM PC)
  560.                      Addison-Wesley (1985)
  561.  
  562.  
  563.               Wirth's book is a good reference source for binary trees
  564.          and data structures.  Hunt's C Toolbox contains useful C
  565.          programming concepts with carefully constructed programming
  566.          examples.
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577.  
  578.  
  579.  
  580.                                     Page 10
  581.  
  582.  
  583.